//
//  main.c
//  C
//
//  Created by edz on 2020/6/19.
//  Copyright © 2020 edz. All rights reserved.
//

#include <stdio.h>
#if 0
int main(int argc, const char * argv[]) {
    int i=0,sum=0;
    /*
    for (i = 1; i <= 100; i = i+1) {
        if (i % 2 == 0) {           //i & 1 == 0
            sum = sum + i;
        }
    }
     */
    while (i<=100) {
        if (i % 2 == 0) {           //i & 1 == 0
            sum = sum + i;
        }
        i = i+1;
    }
    printf("%d\n",sum);
    return 0;
}
#endif

#if 0
int main(){
    printf("* * * *\n");
    printf(" * * * \n");
    printf("  * *  \n");
    printf("   *   \n");
    return 0;
}
#endif

#if 0
int main(){
    float f,c;
    printf("请输入华氏温度：");
    scanf("%f",&f);
    c = 5*(f-32)/9;
    printf("%.2f对应的摄氏温度是%.2f\n",f,c);
    return 0;
}
#endif

#if 0
int main(){
    double x,y;
    printf("请输入用水量：");
    scanf("%lf",&x);
    if (x < 0) {
        printf("用水量不能是负数！\n");
        return -1;
    }
    if (x<=15) {
        y = 4 * x /3;           //y = 4.0 / 3 * x
    }
    else
        y = 2.5 * x - 10.5;
    printf("水费为%.2lf\n",y);
    return 0;
}
#endif

#if 0
int main(){
    double x,y;
    scanf("%lf",&x);
    if (x == 0) {
        y = x;
    }
    else
        y = 1/x;
    printf("y = %lf\n",y);
    return 0;
}
#endif

#if 0
#include <math.h>
int main(){
    int money,year;
    double rate,sum;
    printf("请输入存款金额：");
    scanf("%d",&money);
    printf("请输入存期：");
    scanf("%d",&year);
    printf("请输入年利率：");
    scanf("%lf",&rate);
    sum = money * pow((1 + rate), year);
    printf("存款到期时本息合计为：%.2lf\n",sum);
    return 0;
}
#endif

#if 0
int main(){
    int n,sum=0;
    scanf("%d",&n);
    for (int i = 1; i <= n; i++) {
        sum = sum + i;
    }
    printf("sum = %d\n",sum);
    return 0;
}
#endif

#if 0
// 求 1-1/3+1/5-1/7+1/9……前n项的和
int main(){
    int n,flag=1;
    double sum = 0 ,item = 0;
    scanf("%d",&n);
    for (int i = 1; i <= n; i++) {
        item = 1.0 / (2 * i - 1);
        sum = sum + flag * item;
        flag = -flag;
    }
    printf("sum = %lf\n",sum);
    printf("pi = %lf\n",sum*4);
    return 0;
}
#endif

#if 0
int main(){
    float x;
    printf("请输入一个实数：");
    scanf("%f",&x);
    if (x >= 0) {
        printf("它的绝对值是%f\n",x);
    }
    else
        printf("它的绝对值是%f\n", -x);
    return 0;
}
#endif

#if 0
int main(){
    double x,y;
    printf("请输入用水量：");
    scanf("%lf",&x);
    if (x < 0) {
        y = 0;
    }
    else if (x <= 15){
        y = 4 * x / 3;
    }
    else
        y = 2.5 * x - 10.5;
    printf("水费是%lf\n",y);

    return 0;
}
#endif


#if 0
// 月份判断
int main(){
    int mouth,day=0;
    printf("请输入月份：");
    scanf("%d",&mouth);
    if (mouth == 1 || mouth == 3 || mouth == 5 || mouth == 7 || mouth == 8 || mouth == 10 || mouth == 12) {
        day = 31;
    }
    else if ( mouth == 4 || mouth == 6 || mouth == 9 || mouth == 11){
        day = 30;
    }
    else
        day = 28;
    printf("这个月有%d天\n",day);
    return 0;
}
#endif

#if 0
// 润年判断
int main(){
    int year;
    printf("请输入年份：");
    scanf("%d",&year);
    if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) {
        printf("该年份是润年\n");
    }
    else
        printf("该年份不是润年\n");
    return 0;
}
#endif


#if 0
int main(){
    double a,b;
    char op;
    printf("Type in an expression:");
    scanf("%lf%c%lf",&a,&op,&b);
    switch (op) {
        case '+':
            printf("=%.2lf\n",a + b);
            break;
        case '-':
            printf("=%.2lf\n",a - b);
            break;
        case '*':
            printf("=%.2lf\n",a * b);
            break;
        case '/':
            printf("=%.2lf\n",a / b);
            break;
        default:
            printf("unknown operator\n");
            break;
    }
    return 0;
}
#endif




// 第四章
#if 0
// 求pi （最后一项绝对值<0.0001）
#include <math.h>
int main(int argc, const char * argv[]) {
    double sum = 0 , item = 1.0;
    int denominater = 1 , flag = 1;
    while ( fabs(item) >= 0.0001) {
        item = flag * 1.0 / denominater;
        sum = sum + item;
        flag = -flag;
        denominater = denominater + 2;
    }
    printf("PI = %lf\n" , sum * 4);
    return 0;
}
#endif


#if 0
// 统计学生成绩
int main(){
    int num , failed;
    double grade , sum;
    num = failed = 0;
    sum = 0;
    printf("Enter grade:");
    scanf("%lf",&grade);
    while ( grade >= 0) {
        num ++;
        sum = sum + grade;
        if (grade < 60) {
            failed ++;
        }
        printf("Enter grade:");
        scanf("%lf", &grade);
    }
    if (num != 0)
    printf("Grade average is %f\n",sum / num);
    printf("Number of failures is %d\n",failed);
    return 0;
}
#endif



#if 0
// 计算整数的位数
int main(){
    int number , count = 0;
    printf("请输入一个整数：");
    scanf("%d" , &number);

    do {
        count ++ ;
        number = number / 10;
    } while (number != 0);
    printf("这个整数有%d位\n", count);
    return 0;
}
#endif



#if 0
// 素数判断(可以使用标志位flag 来判断)
int main(){
    int i , m;
    printf("请输入一个正整数：");
    scanf("%d",&m);
    for (i = 2; i <= m/2; i++) {
        if (m % i == 0)
            break;
    }
    if ( i > m/2 && m != 1) {
        printf("这个数是素数\n");
    }
    else
        printf("这个数不是素数\n");
    
    return 0;
}
#endif


#if 0
// n个成绩最高分
int main(){
    int n , i , mark , max;
    printf("请输入成绩个数：");
    scanf("%d", &n);
    printf("请输入成绩：");
    scanf("%d", &mark);
    max = mark;
    for ( i = 1; i < n; i++) {
        printf("请输入成绩：");
        scanf("%d", &mark);
        if (mark > max) {
            max = mark;
        }
    }
    printf("最高成绩为%d\n",max);
    return 0;
}
#endif


#if 0
// 将整数按照数字逆序输出
int main(){
    int x;
    printf("请输入一个整数：");
    scanf("%d",&x);
    if (x == 0) {
        printf("0");
    }
    else if (x > 0){
        while ( x != 0) {
            printf("%d",x % 10);
            x = x / 10;
        }
    }
    else{
        printf("-");
        x = -x;
        while (x != 0) {
            printf("%d",x % 10);
            x = x / 10;
        }
    }
    
    printf("\n");
    return 0;
}
#endif


#if 0
//求100以内的素数，每行输出10个
int main(){
    int i , j , count = 0;
    for (i = 1; i <= 100; i++) {
        for (j = 2; j <= i/2 ; j++) {
            if (i % j == 0) {
                break;
            }
        }
        if ( j > i/2 && i != 1) {
            printf("%d,",i);
            count++;
            if (count % 10 == 0) {
                printf("\n");
            }
        }
    }
    printf("\n");
    return 0;
}
#endif


#if 0
// 计算并输出 斐波那契数列前十项
int main(){
    int x1,x2,x,i;
    x1 = x2 = 1;
    printf("%4d%4d",x1 ,x2);
    for (i = 3 ; i <= 10; i++) {
        x = x1 + x2;
        printf("%4d",x);
        x1 = x2;
        x2 = x;
    }
    printf("\n");
    return 0;
}
#endif



// 第六章 函数
#if 0
// 判断奇偶的函数
int even(int n){
    if ( n % 2 == 0) {
        return 1;
    }
    else
        return 0;
}
#endif


#if 0
// 定义函数funpi，求pi近似值
#include <math.h>
double funpi(double e){
    int denominator = 1,flag =1;
    double item = 1,sum = 0;
    while (fabs(item) >= e) {
        item = flag * 1.0 / denominator;
        sum = sum + item;
        flag = -flag;
        denominator = denominator + 2;
    }
    return sum*4;
}
#endif

#if 0
// 素数
int isPrime(int n){
    int flag = 1;
    for (int i = 2 ; i <= n/2; i++) {
        if (n % i == 0) {
            flag = 0;
            break;
        }
    }
    return flag;
}
int main (){
    int n;
    scanf("%d",&n);
    if (isPrime(n)) {
        printf("这个数是素数!\n");
    }
    else
        printf("这个数不是素数!\n");
    return 0;
}
#endif


#if 0
// 输出数字金字塔
void pyramid(int n){
    int i,j;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n-i; j++) {
            printf(" ");
        }
        for (j = 1; j <= i; j++) {
            printf("%d ",i);
        }
        printf("\n");
    }
}

int main(){
    int n;
    scanf("%d",&n);
    pyramid(n);
    return 0;
}
#endif


#if 0
// 阶乘
int fact(int n){
    int fact = 1;
    for (int i = 1; i <= n ; i++) {
        fact = fact * i;
        //fact *= i;
    }
    return fact;
}
#endif

#if 0
int main(){
    short a=-1;
    unsigned short b,c;
    b = a;
    printf("%x\n",b);
    c = a + 1;
    printf("%x\n",c);
    c = a + c;
    printf("%x\n",c);
    return 0;
}
#endif


#if 0
// 大小写转换
void characters(void);

int main(){
    characters();
    return 0;
}

void characters(void){
    char ch;
    while ((ch = getchar()) != '\n') {
        if (ch >= 'A' && ch <= 'Z') {
            ch = ch + 'a' - 'A';
        }
        if (ch >= 'a' && ch <= 'z') {
            ch = ch + 'A' - 'a';
        }
        putchar(ch);
    }
    printf("\n");
}
#endif


#if 0
char characters(char ch);

int main(){
    char c;
    while ((c = getchar()) != '\n') {
        characters(c);
    }
    printf("\n");
    return 0;
}

char characters(char ch){
    if (ch >= 'A' && ch <= 'Z') {
        ch = ch + 'a' - 'A';
    }
    if (ch >= 'a' && ch <= 'z') {
        ch = ch + 'A' - 'a';
    }
    putchar(ch);
    return ch;
}
#endif



// 第五章 数组

#if 0
int main(){
    int i;
    int fib[10] = {1,1};
    for (i = 2; i < 10; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    for (i = 0; i < 10; i++) {
        printf("%d ",fib[i]);
    }
    printf("\n");
    return 0;
}
#endif


#if 0
// 选择排序
#include <time.h>    // time
#include <stdlib.h> // rand , srand

void printArray(int a[], int n);

int main(){
    int a[10];
    srand((unsigned int)time(NULL));
    int temp;
    for (int i = 0; i < 10; i++) {
        a[i] = rand() % 100;
    }
    printArray(a, 10);
    for (int i = 0; i < 10; i++) {
        for (int j = i+1; j < 10; j++) {
            if (a[j] < a[i]) {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    printArray(a, 10);
    return 0;
}

void printArray(int a[], int n){
    for (int i = 0; i < n; i++) {
        printf("%4d",a[i]);
    }
    printf("\n");
}
#endif


#if 0
// 选择排序
#include <time.h>
#include <stdlib.h>

void find_and_mov_min(int a[ ], int n)
{
   int imin = 0, i;
   int temp;

   for( i=1; i<n; i++ )
      if( a[i]<a[imin] ) imin = i;

    temp = a[0];  a[0] = a[imin]; a[imin] = temp;
}

void printArray(int a[], int n) {
    for (int i = 0; i < n; i++)
        printf("%4d", a[i]);
    printf("\n");
}

int main(void)
{
    int a[10];
    // 构造随机数队列
    srand((unsigned int)time(NULL));
    for (int i = 0; i < 10; i++)
        a[i] = rand() % 100;
    
    printArray(a, 10);
    
    for(int i = 0; i < 9; i++) {
        find_and_mov_min(a + i, 10 - i);
        printArray(a, 10);
    }
    /*
    find_and_mov_min(a, 10);
    printArray(a, 10);
    
    find_and_mov_min(a + 1, 9);
    printArray(a, 10);
    */
}
#endif


#if 0
#include <time.h>
#include <stdlib.h>

void printArray(int a[], int n) {
    for (int i = 0; i < n; i++)
        printf("%4d", a[i]);
    printf("\n");
}

void printArray2(int a[], int r, int c) {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++)
            printf("%4d", a[i * c + j]);
        printf("\n");
    }
    printf("\n");
}

int main(void)
{
    int a[3][2];
    // 构造随机数队列
    srand((unsigned int)time(NULL));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 2; j++) {
            a[i][j] = rand() % 100;
        }
    }
    
    int imin = 0;
    int jmin = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 2; j++) {
            if (a[i][j] < a[imin][jmin]) {
                imin = i;
                jmin = j;
            }
        }
    }

    printArray2((int*) a, 3, 2);
    
    printf("min is %d %d\n", imin, jmin);
    
}
#endif



#if 0
// 判断回文
int main(){
    int n = 0;
    char s[20];
    int flag = 1;
    printf("Enter a string:");
    while ((s[n] = getchar()) != '\n') {
        n++;
    }
    s[n] = '\0';        // s[n] = 0;
    printf("n = %d\n" , n);
    printf("%s\n",s);
    for (int i=0 ; i <= n/2 - 1 ; i++) {
        if (s[i] != s[n-1-i]) {
            flag = 0;
            break;
        }
    }
    if (flag == 1) {
        printf("是回文\n");
    }
    else
        printf("不是回文\n");
    return 0;
}
#endif


#if 0
int strlenth(char s[]);
int main(){
    char s[10] = "happy";
    printf("%d\n",strlenth(s));
    return 0;
}

int strlenth(char s[]){
    int n=0;
    while (s[n] != '\0') {
        n++;
    }
    return n;
}
#endif


// ******************************************************************************
#if 0
// 字符串编程：进制转换
#include <math.h>
#define NUMBER 80
int main(){
    int i=0,n=0;
    char str[NUMBER];
    // 初始化str(输入)
    while ((str[i] = getchar()) != '\n') {
        i++;
    }
    str[i] = 0;
    printf("%s\n",str);
    
    // 把16进制符号放入新的数组new[]
    
    char new[NUMBER];
    for (i = 0; str[i] != 0; i++) {
        if ((str[i] >= '0' &&  str[i] <= '9')||
            (str[i] >= 'a' &&  str[i] <= 'f')||
            (str[i] >= 'A' &&  str[i] <= 'F')) {
            new[n] = str[i];
            n++;
        }
    }
    new[n] = 0;
    printf("%s\n",new);
    
    // 16进制转换为10进制
    int d = 0;
    for (int j = 0; j < n; j++) {
        if (new[j] >= '0' && new[j] <= '9') {
            new[j] = new[j] - '0';
            d += new[j] * pow(16, n-1-j);
        }
        else if (new[j] >= 'a' && new[j] <= 'z') {
            new[j] = new[j] - 'a' + 10;
            d += new[j] * pow(16, n-1-j);
        }
        else{
            new[j] = new[j] - 'A' + 10;
            d += new[j] * pow(16, n-1-j);
        }
        
    }
    printf("%d\n",d);
    return 0;
}

// 256*10 + 16*13 + 15
// 2560 + 208 + 15
#endif
// *******************************************************************************


#if 0
// 随机数分布图
#include <time.h>
#include <stdlib.h>
#define NUMBER 100

int main(){
    int s[NUMBER];
    int fenbu[11] = {0};
    srand((unsigned int)time(NULL));
    for (int i = 0; i < NUMBER ; i++) {
        s[i] = rand() % 100;
        printf("%d ",s[i]);
        fenbu[s[i] / 10]++;
    }
    printf("\n");
    int a=0,b=0;
    
    for (int i = 0; i < 11; i++) {
        if (fenbu[i] > a) {
            a = b = fenbu[i];
        }
    }
    for (int i = 0; i < a; i++) {
        for (int j = 0; j < 11; j++) {
            if (fenbu[j] >= b) {
                printf(" *  ");
            }
            else
                printf("    ");
        }
        b--;
        printf("\n");
    }
    for (int i = 0; i <= 10; i++) {
        printf(" %d ",i * 10);
    }
    printf("\n");
    return 0;
}
#endif

// *********************************************************************************
// 7月1日

#if 0
// 二维数组的示例
#include <time.h>
#include <stdlib.h>

void print2dArray(int a[][3],int r);
void transpose(int a[][3],int r);

int main(){
    // 1. 随机生成一个4*3的二维数组
    int a[4][3];
    srand((unsigned int) time(NULL));
    for (int i = 0; i < 4; i++) {
        for (int j = 0 ; j < 3; j++) {
            a[i][j] = rand() % 100;
            printf("%4d",a[i][j]);
        }
        printf("\n");
    }
    printf("*************\n");
    // 2. 打印这个二维数组
    print2dArray(a, 4);
    printf("*************\n");
    // 3. 按照列输出
    transpose(a, 4);
    return 0;
}


void print2dArray(int a[][3],int r){
    for (int i = 0; i < r; i++) {
        for (int j = 0 ; j < 3; j++) {
            printf("%4d",a[i][j]);
        }
        printf("\n");
    }
}

void transpose(int a[][3],int r){
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < r; j++) {
            printf("%4d",a[j][i]);
        }
        printf("\n");
    }
}
#endif


#if 0
unsigned int my_strlen(char s[]);
void my_strcopy(char s[],char t[]);
int my_strcmp(char a[],char b[]);
void my_strcat(char a[],char b[]);

int main(){
    char s[20] = "HAPPY";
    // 计算字符串长度
    unsigned int len = my_strlen(s);
    printf("length is %d\n",len);
    
    // 字符串拷贝
    char s2[20];
    my_strcopy(s, s2);
    printf("s2 is %s\n",s2);
    
    // 字符串比较
    char s3[20] = "HAPPY";
    printf("%d\n",my_strcmp(s, s3));
    
    // 字符串追加
    char s4[20] = "BIRTHDAY";
    my_strcat(s, s4);
    printf("%s\n",s);
    return 0;
}


// 计算输入的字符串中第一个0之前有多少字符
unsigned int my_strlen(char s[]){
    int n = 0;
    while (s[n] != 0) {
        n++;
    }
    return n;
}

void my_strcopy(char s[],char t[]){
    for (int i = 0; i < my_strlen(s)+1; i++) {
        t[i] = s[i];
    }
    /*
    int i = 0;
    while (s[i] != 0) {
        t[i] = s[i];
        i++;
    }
    t[i] = 0;
     */
    
    /*
    int i = -1;
    do{
        i++;
        t[i] = s[i];
    }while(s[i] != 0);
     */
    
    /*少赋值最后一个
    int i = 0;
    do{
        t[i] = s[i];
        i++;
    }while(s[i] != 0);
     */
    
    /*
    int i = 0;
    while (t[i] = s[i] != 0) {
        i++;
    }
     */
}

/*
 return 0 相等
 1:a>b
 0:a=b
 -1:a<b
 */
int my_strcmp(char a[],char b[]){
    int i = 0;
    while (a[i] == b[i]) {
        if (a[i] == 0) {
            return 0;
        }
        i++;
    }
    if (a[i] > b[i]) {
        return 1;
    }
    else
        return -1;
}

/*
 b->a: a+b
 a:abc b:def -> a:abcdef
 */
void my_strcat(char a[],char b[]){
    // 1. 找到a[]中0的位置
    int i=0;
    while (a[i] != 0) {
        i++;
    }
    // 2. 把b复制到a中0开始的地方
    int j = 0;
    while (b[j] != 0) {
        a[i+j] = b[j];
        j++;
    }
    a[i+j] = 0;
}
#endif


// ********************************************************************************
// 7月2日

#if 0
void swap1(int *x,int *y){
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

int main(){
    int a = 1;
    int b = 2;
    swap1(&a, &b);
    printf("%d    %d\n",a,b);
}
#endif


#if 0
int main(){
    int a[100];
    int* p = a;
    int* q = &a[4];
    printf("%ld\n",q - p);
    printf("%d\n",(int)q - (int)p);
    return 0;
}
#endif


#if 0
// 编写函数将数组逆序
void reverse(int a[],int n){
    int i , k , t;
    for (i = 0, k = n-1; i < k; i++,k--) {
        t = a[i];
        a[i] = a[k];
        a[k] = t;
    }
}

int main(){
    int a[10],k;
    for (k=0; k<10; k++) {
        a[k] = k;
        printf("%d  ",a[k]);
    }
    printf("\n");
    reverse(a + 1, 9);
    for (k=0; k<10; k++) {
        printf("%d  ",a[k]);
    }
    printf("\n");
    return 0;
}
#endif


#if 0
void entrypt(char *s){
    for (; *s; s++) {
        *s = ((*s == 'z') ? *s = 'a' : (*s) + 1);
    }
}
int main(){
    char pwd[100];
    scanf("%s",pwd);
    entrypt(pwd);
    puts(pwd);
}
#endif



#if 0
// 指针完成 strcpy;strcmp;strlen;strcat

void my_strcpy(char *s,char *t);
int my_strlen(char* s);
int my_strcmp(char* s,char* c);
void my_strcat(char* s,char* c);

int main(){
    char s[20] = "HAPPY";
    // 计算字符串长度
    unsigned int len = my_strlen(s);
    printf("length is %d\n",len);
    
    // 字符串拷贝
    char s2[20];
    my_strcpy(s, s2);
    printf("s2 is %s\n",s2);
    
    // 字符串比较
    char s3[20] = "HAPPY";
    printf("%d\n",my_strcmp(s, s3));
    
    // 字符串追加
    char s4[20] = "BIRTHDAY";
    my_strcat(s, s4);
    printf("%s\n",s);
    return 0;
}

void my_strcpy(char *s,char *t){
    while ( *s ) {
        *t = *s;
        s++;
        t++;
    }
    *t = 0;
}

int my_strlen(char* s){
    int n = 0;
    while ( *s ) {
        n++;
        s++;
    }
    return n;
}


int my_strcmp(char* s,char* c){
    while (*s == *c) {
        if (*s == 0) {
            return 0;
        }
        s++;
        c++;
    }
    if (*s > *c) {
        return 1;
    }
    else
        return -1;
    return 0;
}


void my_strcat(char* s,char* c){
    // 1. 找到a[]中0的位置
    while (*s) {
        s++;
    }
    // 2. 把b复制到a中0开始的地方
    while (*c) {
        *s = *c;
        s++;
        c++;
    }
    *s = 0;
}
#endif


// *********************************************************************************
/* 7月3日*/
#if 0
#include <string.h>
struct student{
    char name[20];
    char* SchoolName;
    int age;
    int id;
};

int main (){
    struct student a;
    a.age = 23;
    a.id = 170801202;
    strcpy(a.name, "liuyuan");
    a.SchoolName = "banyuan";
    return 0;
}
#endif



#if 0
/**
 * @author      : banyuan (linch1982@gmail.com)
 * @file        : struct_array
 * @created     : Friday Jul 03, 2020 13:53:29 CST
 * @purpose     : 结构体数组示例
 */

#include <stdio.h>
#include <string.h>
#include <string.h>
#include <stdlib.h>

#define LEN 10

typedef struct student {
    char name[20];
    char* schoolName;
    int grade;
    int age;
    int id;
} Student;

void printStudent(Student s) {
    printf("*********\n");
    printf("name: %s\n", s.name);
    printf("grade: %d\n", s.grade);
}

void printStudents(Student s[], int n) {
    for (int i = 0; i < n; i++) {
        printStudent(s[i]);
    }
}

// 初始化学生信息的数组
void initStudents(Student s[], int n) {
    for (int i = 0; i < n; i++) {
        s[i].grade = rand()%101;
        for (int j = 0; j < 4; j++) {
            s[i].name[j] = (rand()%26) + 'a';
        }
        s[i].name[4] = '\0';
    }
}

void sort(Student s[], int n){
    for (int i = 0; i < n-1; i++) {
        int max = i;
        for (int j = i+1; j < n; j++) {
            if (s[j].grade > s[max].grade)
                max = j;
        }
        if (max != i) {
            // 交换max和i的信息
            Student t = s[i];
            s[i] = s[max];
            s[max] = t;
        }
    }
}

int main() {
    Student s[LEN];
    initStudents(s, LEN);
//    printStudents(s, LEN);
    sort(s, LEN);
    printStudents(s, LEN);
}
#endif



/*
 * ============================================================================
 *
 *       Filename:  arrayList.c
 *
 *    Description:  顺序表的示例
 *
 *        Version:  1.0
 *        Created:  07/06/2020 10:12:20 AM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  lin chuan , linch1982@gmail.com
 *   Organization:
 *
 * ============================================================================
 */
// 7月6日

#if 0
#include <stdio.h>
#include <stdlib.h>

typedef struct arrayList {
    int * head; // 容纳元素的数组
    int length; // 当前已有元素的个数
    int capacity; // 最多能容纳元素的个数
} ArrayList;

ArrayList initArrayList(int capacity);
void printArrayList(ArrayList l);
void insert(ArrayList *l, int value, int pos);

ArrayList initArrayList(int capacity) {
    ArrayList l;
    l.capacity = capacity;
    l.head = malloc(sizeof(int) * l.capacity);
    l.length = 0;
    return l;
}

// 打印ArrayList
void printArrayList(ArrayList l) {
    for (int i = 0; i < l.length; i++) {
        printf("%4d", l.head[i]);
    }
    printf("\n");
}

// 将一个元素插入到list中的position位置
void insert(ArrayList* l, int value, int pos) {
    if (pos > l->length || pos < 0) {
        // 非法的位置
        printf("pos: %d 非法，length为: %d\n", pos, l->length);
        return;
    }

    if (l->length == l->capacity) {
        // list满了
        l->head = realloc(l->head, l->capacity*2*sizeof(int));
        /*
        int* new = malloc(sizeof(int) * l->capacity * 2);
        // copy old to new
        for (int i = 0; i < l->capacity; i++) {
            new[i] = l->head[i];
        }
        free(l->head);
        l->head = new;
        */
        //l->capacity *= 2;
        l->capacity <<= 1;
    }

    for (int i = l->length-1; i >= pos; i--) {
        l->head[i+1] = l->head[i];
    }
    l->head[pos] = value;
    l->length++;
}


void delete(ArrayList* l,int pos){
    for (int i = pos; i < l->length - 1; i++) {
        l->head[i] =l->head[i+1];
    }
    l->length--;
}

int search(ArrayList* l, int value){
    for (int i = 0; i < l->length ; i++) {
        if (l->head[i] == value) {
            return i;
        }
    }
    return -1;
}


void modify(ArrayList* l , int value , int pos){
    l->head[pos] = value;
}

int main() {
    ArrayList l = initArrayList(4);
    insert(&l, 100, 0);
    insert(&l, 200, 0);
    insert(&l, 300, 0);
    insert(&l, 400, 0);
    insert(&l, 500, 0);
    delete(&l, 0);
    delete(&l, 0);
    modify(&l, 600, 0);
    printArrayList(l);
    printf("200在第%d个位置\n",search(&l, 200));
    return 0;
}
#endif



// 链表
#if 0
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int elem;
    struct node *next;
}Node, LinkedList;

LinkedList* initLinkedList(void);
void printLinkedList(LinkedList* l);
Node* find(LinkedList* l,int pos);
void insertLinkedList(LinkedList* l , int value, int pos);
void delete(LinkedList* l , int pos);
Node* search(LinkedList* l , int value);
void modify(LinkedList* l , int pos, int value);

int main(){
    LinkedList* head = initLinkedList();
    insertLinkedList(head, 100, 0);
    insertLinkedList(head, 200, 1);
    insertLinkedList(head, 300, 2);
    insertLinkedList(head, 400, 3);
    delete(head, 3);
    modify(head, 2, 400);
    printLinkedList(head);
    return 0;
}

LinkedList* initLinkedList(){
    Node* head = malloc(sizeof(Node));
    head->elem = 0;//head里面的elem表示链表中有多少元素
    head->next = NULL;
    return head;
}

void printLinkedList(LinkedList* l){
    Node* temp = l->next;
    while (temp != NULL) {
        printf("%4d",temp->elem);
        temp = temp->next;
    }
    printf("\n");
}

//在l中查找第pos个节点，并返回
Node* find(LinkedList* l,int pos){
    Node* temp = l->next;
    while ( pos>0 ) {
        temp = temp->next;
        pos--;
    }
    return temp;
}

void insertLinkedList(LinkedList* l , int value, int pos){
    if (pos > l->elem || pos < 0) {
        printf("pos: %d 非法,length 为:%d\n",pos , l->elem);
        return;
    }
    
    Node* pNew = malloc(sizeof(Node));
    pNew->elem = value;
    
    Node* pre ;
    if(pos == 0){
        // 插入的位置是0，表示首元素
        pre = l;
    }else{
        pre = find(l, pos-1);
    }
    pNew->next = pre->next;
    pre->next = pNew;
    
    l->elem++;
}


void delete(LinkedList* l , int pos){
    if (pos > l->elem || pos < 0) {
        printf("pos: %d 非法,length 为:%d\n",pos , l->elem);
        return;
    }
    Node* pre;
    if(pos == 0){
        // 插入的位置是0，表示首元素
        pre = l;
    }else{
        pre = find(l, pos-1);
    }
    pre->next = pre->next->next;
    
    l->elem--;
}

Node* search(LinkedList* l , int value){
    Node* temp = l->next;
    for (int i = 0; i < l->elem; i++) {
        if (temp->elem == value) {
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}

void modify(LinkedList* l , int pos, int value){
    find(l, pos)->elem = value;
}
#endif




// 7月7日

#if 0
// 循环结构(约瑟夫环)

#include <stdlib.h>
#include <stdio.h>

typedef struct node{
    int elem;
    struct node *next;
} Node , Circlelist;

Circlelist* init(void);
Node* gettail(Circlelist* l);
void addAtHead(Circlelist* l , int value);
void addAtTail(Circlelist* l , int value);
void print(Circlelist* l);
void print2(Circlelist* l);
void josephus(Circlelist* l,int num);

int main(){
    Circlelist* l = init();
    for (int i = 6; i >= 1; i--) {
        addAtHead(l, i);
    }
    print(l);
    josephus(l, 4);
    return 0;
}

Circlelist* init(void){
    Circlelist* l = malloc(sizeof(Circlelist));
    l->elem = 0;        // 表头的elem表示该循环链表里面有多少元素
    l->next = NULL;
    return l;
}

void print(Circlelist* l){
    Circlelist* p = l->next;
    for (int i = 0; i < l->elem; i++) {
        printf("%4d",p->elem);
        p = p->next;
    }
    printf("\n");
}

// 当打印完最后一个元素的时候表示打印结束
void print2(Circlelist* l){
    Circlelist* p = l->next;
    if (p == NULL) {
        return;
    }
    while (p->next != l->next) {
        printf("%4d",p->elem);
        p = p->next;
    }
    printf("%4d\n",p->elem);
    
//    do {
//        printf("%4d",p->elem);
//
//    } while ((p = p->next) && (p->next != l->next));
}

Node* gettail(Circlelist* l){
    Node* p = l->next;
    if (p == NULL) {
        return NULL;
    }
    while (p->next != l->next) {
        p = p->next;
    }
    return p;
}

void addAtHead(Circlelist* l , int value){
    Node* new = malloc(sizeof(Node));
    Node* tail = gettail(l);
    new->elem = value;
    // 1. new 指向现有的0号元素
    new->next = l->next;
    // 2. l 指向new
    l->next = new;
    // 3. tail 指向new
    if (tail == NULL) {
        // 现在是空链表,新增元素是第0个元素
        new->next = new;
    }
    else{
        tail->next = new;
    }
    l->elem++;
}


void addAtTail(Circlelist* l , int value){
    
}

void josephus(Circlelist* l,int num){
    int i = 1;
    Node* p = l->next;
    while (l->elem != 0) {
        // 找出第num个元素打印并删除
        while (i != num-1) {
            p = p->next;
            i++;
        }
        printf("%4d\n",p->next->elem);
        p->next = p->next->next;
        l->elem--;

        p = p->next;
        i=1;
    }
    l->next = NULL;
}
#endif


//*************************************************************************************
#if 0
// 链栈
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node{
    int elem;
    struct node *next;
}Node, LinkedList,Stack;

LinkedList* init(void);
void print(LinkedList* l);
Node* find(LinkedList* l,int pos);
void insertLinkedList(LinkedList* l , int value, int pos);
void delete(LinkedList* l , int pos);
Node* search(LinkedList* l , int value);
void modify(LinkedList* l , int pos, int value);

void push(Stack* s,int value);
int pop(Stack* s);
int peep(Stack* s);
int isEmpty(Stack* s);
int isOperator(char* s);

int main(){
    Stack* s = init();
//    for (int i = 1; i < 10; i++) {
//        push(s, i);
//    }
//
//    while ( !isEmpty(s) ) {
//        int v =pop(s);
//        printf("%d\n",v);
//    }
//    printf("\n");
    
    char* a[] = {"5","1","2","+","4","*","+","3","-"};
    int strNum = sizeof(a) / sizeof(a[0]);
    for (int i = 0 ; i < strNum; i++) {
        // 处理每个输入的字符串
        if (isOperator(a[i])) {
            // 运算符
            int r = pop(s);
            int l = pop(s);
            int result;
            // 运算
            switch (a[i][0]) {
                case '+':
                    result = l + r;
                    break;
                case '-':
                    result = l - r;
                    break;
                case '*':
                    result = l * r;
                    break;
                case '/':
                    result = l / r;
                    break;
                default:
                    printf("未知操作符%s\n",a[i]);
                    return -1;
            }
            push(s, result);
        }
        else{
            // 数字
            push(s, atoi(a[i]));
        }
    }
    int last = pop(s);
    printf("%d\n",last);
    return 0;
}

void push(Stack* s,int value){
    insertLinkedList(s, value, 0);
}

int pop(Stack* s){
    int r = s->next->elem;
    delete(s, 0);
    return r;
}

int peep(Stack* s){
    return s->next->elem;
}

int isEmpty(Stack* s){
    return (s->next == NULL);
}

int isOperator(char* s){
    // "-" -> 1
    // "1" -> 0
    // 此处未判断空字符串
    if (strlen(s) > 1) {
        return 0;
    }
    if (s[0] >= '0' && s[0] <= '9') {
        return 0;
    }
    else
        return 1;
}

LinkedList* init(){
    Node* head = malloc(sizeof(Node));
    head->elem = 0;//head里面的elem表示链表中有多少元素
    head->next = NULL;
    return head;
}

void print(LinkedList* l){
    Node* temp = l->next;
    while (temp != NULL) {
        printf("%4d",temp->elem);
        temp = temp->next;
    }
    printf("\n");
}

//在l中查找第pos个节点，并返回
Node* find(LinkedList* l,int pos){
    Node* temp = l->next;
    while ( pos>0 ) {
        temp = temp->next;
        pos--;
    }
    return temp;
}

void insertLinkedList(LinkedList* l , int value, int pos){
    if (pos > l->elem || pos < 0) {
        printf("pos: %d 非法,length 为:%d\n",pos , l->elem);
        return;
    }
    
    Node* pNew = malloc(sizeof(Node));
    pNew->elem = value;
    
    Node* pre ;
    if(pos == 0){
        // 插入的位置是0，表示首元素
        pre = l;
    }else{
        pre = find(l, pos-1);
    }
    pNew->next = pre->next;
    pre->next = pNew;
    
    l->elem++;
}


void delete(LinkedList* l , int pos){
    if (pos > l->elem || pos < 0) {
        printf("pos: %d 非法,length 为:%d\n",pos , l->elem);
        return;
    }
    Node* pre;
    if(pos == 0){
        // 插入的位置是0，表示首元素
        pre = l;
    }else{
        pre = find(l, pos-1);
    }
    pre->next = pre->next->next;
    
    l->elem--;
}

Node* search(LinkedList* l , int value){
    Node* temp = l->next;
    for (int i = 0; i < l->elem; i++) {
        if (temp->elem == value) {
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}

void modify(LinkedList* l , int pos, int value){
    find(l, pos)->elem = value;
}
#endif


/*
 顺序栈（数组）和链栈的区别
顺序表是静态分配的，而链栈是动态分配，链栈可以将很多零碎的空间利用起来，容量可变，节省空间，顺序栈则固定内存空间，容量不变。
 */


// 7月8日
#if 0
#include <stdio.h>
#define SIZE 22

/*入栈*/
int push(int *p, int top, int elem) {
    if (top > 19) {
        printf("栈已满\n");
        printf("%d\n",top);
        return top;
    }
    p[++top] = elem;
    printf("入栈元素：%d，栈顶为：%d\n", elem, top);
    return top;
}

/*出栈*/
int pop(int *p, int top) {
    if (top == -1) {
        printf("空栈\n");
        return -1;
    }

    printf("出栈元素：%d  ", p[top]);
    p[top--] = 0;
    printf("栈顶为：%d\n", top);
    return top;
}

int main() {
    int a[20] = {0};
    int top = -1;

    for (int i = 0; i < SIZE; i++) {
        top = push(a, top, i + 1);
    }

    for (int i = 0; i <= SIZE; i++) {
        top = pop(a, top);
    }

    for (int i = 0; i < SIZE; i++) {
        printf("%d\n", a[i]);
    }

    return 0;
}
#endif


#if 0
// 队列
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct node{
    int elem;
    struct node *next;
}Node, LinkedList,Stack,Queue;

LinkedList* init(void);
void print(LinkedList* l);
Node* find(LinkedList* l,int pos);
void insertLinkedList(LinkedList* l , int value, int pos);
void delete(LinkedList* l , int pos);
Node* search(LinkedList* l , int value);
void modify(LinkedList* l , int pos, int value);

void enqueue(Queue* q, int value);
int dequeue(Queue* q);
bool isEmpty(Queue* q);

int main(){
    Queue* q = init();
    for (int i = 0; i < 10; i++) {
        enqueue(q, i);
    }
    print(q);
    while (!isEmpty(q)) {
        int v = dequeue(q);
        printf("%4d",v);
    }
    printf("\n");
    return 0;
}

void enqueue(Queue* q, int value){
    // q->elem 表示这个队列的长度
    insertLinkedList(q, value, q->elem);
}

int dequeue(Queue* q){
    int r = q->next->elem;
    delete(q, 0);
    return r;
}

bool isEmpty(Queue* q){
    return q->elem == 0;
    // return q->next == NULL;
}


LinkedList* init(){
    Node* head = malloc(sizeof(Node));
    head->elem = 0;//head里面的elem表示链表中有多少元素
    head->next = NULL;
    return head;
}

void print(LinkedList* l){
    Node* temp = l->next;
    while (temp != NULL) {
        printf("%4d",temp->elem);
        temp = temp->next;
    }
    printf("\n");
}

//在l中查找第pos个节点，并返回
Node* find(LinkedList* l,int pos){
    Node* temp = l->next;
    while ( pos>0 ) {
        temp = temp->next;
        pos--;
    }
    return temp;
}

void insertLinkedList(LinkedList* l , int value, int pos){
    if (pos > l->elem || pos < 0) {
        printf("pos: %d 非法,length 为:%d\n",pos , l->elem);
        return;
    }
    
    Node* pNew = malloc(sizeof(Node));
    pNew->elem = value;
    
    Node* pre ;
    if(pos == 0){
        // 插入的位置是0，表示首元素
        pre = l;
    }else{
        pre = find(l, pos-1);
    }
    pNew->next = pre->next;
    pre->next = pNew;
    
    l->elem++;
}


void delete(LinkedList* l , int pos){
    if (pos > l->elem || pos < 0) {
        printf("pos: %d 非法,length 为:%d\n",pos , l->elem);
        return;
    }
    Node* pre;
    if(pos == 0){
        // 插入的位置是0，表示首元素
        pre = l;
    }else{
        pre = find(l, pos-1);
    }
    pre->next = pre->next->next;
    
    l->elem--;
}

Node* search(LinkedList* l , int value){
    Node* temp = l->next;
    for (int i = 0; i < l->elem; i++) {
        if (temp->elem == value) {
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}

void modify(LinkedList* l , int pos, int value){
    find(l, pos)->elem = value;
}
#endif


#if 0
void printArray(int a[],int n);
void selection(int a[] , int n);
void insertion(int a[] , int n);
void bubblesort(int a[] , int n);

#include <time.h>
#include <stdlib.h>
int main(){
    int a[10];
    srand(time(NULL));
    for (int i = 0; i < 10; i++) {
        a[i] = rand() % 100;
    }
    
    printArray(a, 10);
    bubblesort(a, 10);
    printArray(a, 10);
}


void printArray(int a[],int n){
    for (int i = 0; i < n; i++) {
        printf("%4d",a[i]);
    }
    printf("\n");
}

//选择排序
void selection(int a[] , int n){
    int min;
    for (int i = 0; i < n-1; i++) {
        min = i;
        for (int j = i+1; j < n; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        // 交换min和i对应的元素
        if (min != i) {
            int temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
}


// 插入排序
void insertion(int a[] , int n){
    for (int i = 1; i < n; i++) {
        // 将a[i]插入到合适的位置
        int j = i;
        while ((j > 0) && a[j] < a[j-1]) {
            int temp = a[j];
            a[j] = a[j-1];
            a[j-1] = temp;
            j--;
//            if (j == 0) {
//                break;
//            }   // 已经将这个元素放到a[0]
        }
    }
}


// 冒泡排序
void bubblesort(int a[] , int n){
    for (int i = n-1; i > 0 ; i--) {            // i表示未排序的数组中最大的下标
        int sorted = 1;
        for (int j = 0; j < i; j++) {           // 一轮排序将最大的冒泡到最右边
            if (a[j] > a[j+1]) {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                sorted = 0;
            }
        }
        printArray(a, 10);
        if (sorted == 1) {
            break;
        }
    }
}
#endif



// 7月9日

#if 0
// 快速排序
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void printArray(int a[],int n);
void quick(int a[], int n);
void swap(int a[], int i , int j);
int main(){
    int a[10];
    srand(time(NULL));
    for (int i = 0; i < 10; i++) {
        a[i] = rand() % 100;
    }
    
    printArray(a, 10);
    quick(a, 10);
    printArray(a, 10);
}


void printArray(int a[],int n){
    for (int i = 0; i < n; i++) {
        printf("%4d",a[i]);
    }
    printf("\n");
}

void swap(int a[], int i , int j){
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

void quick(int a[], int n){
    // 出口条件：当小于等于一个元素时，无需进行排序
    if (n <= 1) {
        return;
    }
    // 将a[0]放到合适的位置
    // 初始化i和j
    int i = 1;
    int j = n-1;
    while (i <= j) {
        
        //找到一个比a[0]大的i
        while ( i < n && a[i] <= a[0] ) {
            i++;
        }
        
        while ( j > 0 && a[j] > a[0]) {
            j--;
        }
        // 交换i和j
        if (i < j) {
            swap(a, i, j);
        }
    }
    // 交换a[0] 和 a[j]
    if (j != 0) {
        swap(a, 0, j);
    }
    // 处理j的左边和右边
    quick(a, j);
    quick(a+j+1 , n-j-1);
}
#endif


// *************************************************************************************
#if 0
// 树的示例
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int elem;
    struct node* l;
    struct node* r;
} Node, Tree;

Tree* init(void);
Tree* insert(Tree* root, int value);
Node* search(Tree* root,int value);
void print(Tree* root);
void print_nicely(Tree* root);


int main(){
    Tree* tree = init();
    tree = insert(tree, 10);
    print_nicely(tree);
    tree = insert(tree, 5);
    print_nicely(tree);
    tree = insert(tree, 15);
    print_nicely(tree);
    tree = insert(tree, 8);
    print_nicely(tree);
    tree = insert(tree, 12);
    print_nicely(tree);
    Node* n ;
    int x = 15;
    n = search(tree, x);
    if (n != NULL) {
        printf("%d\n",n->elem);
    }
    else
        printf("Not found %d\n",x);
    return 0;
}

Tree* init(void){
    return NULL;
}

Tree* insert(Tree* root, int value){
    Node* newNode = malloc(sizeof(Node));
    newNode->elem = value;
    newNode->l = newNode->r = NULL;
    // root为NULL，表示空树
    if (root == NULL) {
        return newNode;
    }
    // 在已有的数里面添加新节点
    // 1. 查找哪个节点可以挂新节点
    // 2. 挂
    Node* t = root;
    
    while (1) {
        if (value < t->elem) {
            if ( t->l == NULL) {
                t->l = newNode;
                break;
            }
            else
                t = t->l;
        }
        else{
            if ( t->r == NULL) {
                t->r = newNode;
                break;
            }
            else
                t = t->r;
        }
    }
    return root;
}


Node* search(Tree* root,int value){
    if (root == NULL) {
        return NULL;
    }
    
    if (value == root->elem) {
        return root;
    }
    
    if (value < root->elem) {
        return search(root->l, value);
    }
    else
        return search(root->r, value);
}


void print(Tree* root){
    if (root->l != NULL) {
        print(root->l);
    }
    //print(root);
    printf("%4d",root->elem);
    
    if (root->r != NULL) {
        print(root->r);
    }
}


void print_nicely(Tree* root){
    print(root);
    printf("\n");
}
#endif

// *************************************************************************************

#if 0
// 题目：可重复使用的队列(数组)
// 附加题：使用完空间
// 循环队列
#include <stdio.h>
#include <stdlib.h>
#define Size 5
 
int queue[Size];
int top=0;
int end=0;
 
void enqueue(int value)
{
    if(top + Size == end){
        printf("The queue is full!\n");
    }else{
        queue[end] = value;
        end=(end+1) % Size;
    }
}

int dequeue()
{
    int temp;
    if(end == top){
        return -1; // 表示空队列
    }
    temp = queue[top];
    queue[top] = 0;
    top=(top+1) % Size;
    return temp;
    
}
 
int main(){
    for (int i = 0; i < Size; i++) {
        enqueue(i);
    }
    
    for (int i = 0; i < Size; i++) {
        printf("%4d",queue[i]);
    }
    printf("\n");

    for (int i = 0; i<3; i++) {
        dequeue();
    }
    for (int i = 0; i < Size; i++) {
        printf("%4d",queue[i]);
    }
    printf("\n");
    enqueue(10);
    enqueue(10);
    enqueue(10);
    enqueue(10);
    for (int i = 0; i < Size; i++) {
        printf("%4d",queue[i]);
    }
    printf("\n");
    return 0;
}
#endif
